#include <malloc.h>

static unsigned _get_buf_index(int snum_nums, int spart_nums) {
	return snum_nums - spart_nums;
}

static void init_arr(const int num_b[], int init_buf_b[], int max_right_len) {
	int sum = 0;
	for (int i = 0; i < max_right_len; i++) {
		int value = num_b[i];
		sum += value;
		init_buf_b[i] = sum;
	}
}

static int _get_value_row_col(const int num_b[], const int prev_row_b[],
			      int spart_nums, int snum_nums) {
	int sum_right = 0;
	int min_max = 0x7FFFFFFF;
	int prev_snum_nums = snum_nums;
	while (1) {
		prev_snum_nums--;
		int new_value = num_b[prev_snum_nums];
		sum_right += new_value;
		int prev_min_max_index =
			_get_buf_index(prev_snum_nums, spart_nums - 1);
		if (prev_min_max_index < 0) {
			break;
		}
		int prev_min_max = prev_row_b[prev_min_max_index];
		int max_of_both;
		if (sum_right >= prev_min_max) {
			max_of_both = sum_right;
		} else {
			max_of_both = prev_min_max;
		}
		if (max_of_both < min_max) {
			min_max = max_of_both;
		}
		if (sum_right >= prev_min_max) {
			break;
		}
	}
	return min_max;
}

static int _get_min_max_sum(const int num_b[], int num_nums, int part_nums,
			    void* space_p) {
	int max_right_len = num_nums - part_nums + 1;
	int* prev_buf_b = space_p;
	int* buf_b = prev_buf_b + max_right_len;
	init_arr(num_b, buf_b, max_right_len);
	if (part_nums == 1) {
		return buf_b[max_right_len - 1];
	}
	int spart_nums = 2;
	while (spart_nums < part_nums) {
		int* tmp_b = prev_buf_b;
		prev_buf_b = buf_b;
		buf_b = tmp_b;
		int snum_nums = spart_nums;
		do {
			int value_row_col = _get_value_row_col(
				num_b, prev_buf_b, spart_nums, snum_nums);
			int new_index = _get_buf_index(snum_nums, spart_nums);
			buf_b[new_index] = value_row_col;
			snum_nums++;
		} while (snum_nums <= num_nums - part_nums + spart_nums);
		spart_nums++;
	}
	int result = _get_value_row_col(num_b, buf_b, part_nums, num_nums);
	return result;
}

int splitArray(int num_b[], int num_nums, int part_nums) {
	int* space_b = malloc(sizeof(int[2][num_nums - part_nums + 1]));
	int min_max_sum = _get_min_max_sum(num_b, num_nums, part_nums, space_b);
	free(space_b);
	return min_max_sum;
}
